package codeTop;

public class q41 {
    public int firstMissingPositive(int[] nums) {
        int n = nums.length;;
        for(int i=0;i<n;i++){
            if (nums[i] <= 0) {
                nums[i] = n+1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (Math.abs(nums[i]) <= n) {
                nums[Math.abs(nums[i])-1]  = Math.abs(nums[Math.abs(nums[i])-1])*-1;
            }
        }
        for (int i = 0; i < n; i++) {
            if (nums[i] > 0) {
                return i+1;
            }
        }
        return n+1;
    }

    public static void main(String[] args) {
        q41 q = new q41();
        System.out.println(q.firstMissingPositive(new int[]{3, 4, -1, 1}));
    }
}
